package com.company;

/**
 * @author zhf
 * @date 2021/11/22
 */

/**
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母不允许被重复使用。
 *
 */
public class SearchString {
    boolean rel = false;
    public static void main(String[] args) {
        char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "A";
        SearchString searchString = new SearchString();
        boolean ans = searchString.exist(board,word);
        System.out.println(ans);
    }

    public boolean exist(char[][] board, String word) {
        char[] key = word.toCharArray();
        int[][] res = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++){
                if (board[i][j] == key[0]){
                    res[i][j] = 1;
                    dfs(i, j, board, key, res, 1);
                    if (rel) {
                        return rel;
                    }
                    res[i][j] = 0;

                }
            }
        }

        return rel;
    }
    /**
     * 回溯
     */
    /***
     *
     * @param i 左右
     * @param j 上下
     * @param board 需查询的矩阵
     * @param key 目标字符串
     * @param res 特征矩阵
     * @param k 已经验证的长度
     */
    public void dfs(int i, int j, char[][] board, char[] key, int[][] res, int k){
        if (k == key.length) {
            rel = true ;
        }
        /*
        i-1
         */
        if (!rel && i - 1 >= 0 && res[i - 1][j] == 0 && key[k] == board[i - 1][j]){
            res[i - 1][j] = 1;
            dfs(i - 1, j, board, key, res, k + 1);
            res[i - 1][j] = 0;
        }
        /*
        i+1
         */
        if (!rel && i + 1 < board.length && res[i + 1][j] == 0 && key[k] == board[i + 1][j]){
            res[i + 1][j] = 1;
            dfs(i + 1, j, board, key, res, k + 1);
            res[i + 1][j] = 0;
        }
        /*
        j-1
         */
        if (!rel && j - 1 >= 0 && res[i][j - 1] == 0 && key[k] == board[i][j - 1]){
            res[i][j - 1] = 1;
            dfs(i, j - 1, board, key, res, k + 1);
            res[i][j - 1] = 0;
        }
        /*
        j+1
         */
        if (!rel && j + 1 < board[0].length&& res[i][j + 1] == 0 && key[k] == board[i][j + 1]){
            res[i][j + 1] = 1;
            dfs(i, j + 1, board, key, res, k + 1);
            res[i][j + 1] = 0;
        }
    }
}
